package com.vint.leetcode;

import com.vint.common.TreeNode;

/*
 * 1. done
 * 2. easy
 */
public class Leetcode106 {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return buildSub(preorder, 0 , preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	public TreeNode buildSub(int[] pre, int ps, int pe, int[] ino, int is, int ie) {
		if (pe < ps) return null;
		TreeNode root = new TreeNode(ino[ie]);
		if(pe == ps) return root;
		int index = 0;
		for(int i = ps; i<=pe; i++){
			if(pre[i] == ino[ie]){
				index = i;
				break;
			}
		}
		root.left = buildSub(pre, ps, index -1, ino, is, is + index - ps - 1);
		root.right= buildSub(pre, index + 1, pe, ino, is + index - ps, ie -1 );
		return root;
	}
}
